package com.zyk.leetcode;

import java.util.HashSet;

/**
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * @author zhangsan
 * @date 2021/4/7 16:04
 */
public class M0201 {

    // https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
    // 暴力解, HashSet
    public static ListNode removeDuplicateNodes(ListNode head) {
        HashSet<Integer> set = new HashSet<>();
        ListNode cur = head, pre = null;
        while (cur != null) {
            if (set.contains(cur.val)) {
                // xxx
                pre.next = cur.next;
                cur = cur.next;
                continue;
            }
            set.add(cur.val);
            pre = cur;
            cur = cur.next;
        }
        return head;
    }

    // for test
    public static ListNode generateList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode pre = head;
        ListNode cur = null;
        for (int i = 1; i < arr.length; i++) {
            cur = new ListNode(arr[i]);
            pre.next = cur;
            pre = pre.next;
        }
        return head;
    }

    // for test
    public static void main(String[] args) {
        ListNode head = generateList(new int[]{1, 2, 3, 3, 2, 1});

        ListNode newHead = removeDuplicateNodes(head);

        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
        System.out.println();
    }

}
